package com.eloancn.leecode.sort;

import java.util.Arrays;

/**
 * 快速排序
 * 选择基准数字
 * @author lihepeng
 *
 */
public class QuickSort {
	
		public static void quickSort(int[] arrs,int low,int high) {
			int i,j,temp;
			if(low>=high) {
				return ;
			}
		  i = low;
		  j = high;
		  // 以最左边为基准位
			temp = arrs[low];
			while(i<j) {
					/**
					 *   先看右边，依此向左边递减
					 *   先从右边向左边找到小于基准数的数
					 *   当右边的哨兵位置所在的数>基准数的时候
					 *   继续从右向左找（同时j索引-1）
					 *   找到之后跳出while循环
					 */
					while(temp <=arrs[j] &&i<j ) {
						j--;
					}
					arrs[i]=arrs[j];
					// 看左边向右边增长
					while(temp >=arrs[i] && i<j) {
						i++;
					}
					arrs[j] = arrs[i];
					
				}
				arrs[i] = temp;
			quickSort(arrs, low, j-1);
			quickSort(arrs, j+1, high);
		}
		public static void main(String[] args) {
			int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
			QuickSort.quickSort(arr, 0, arr.length-1);
			String s = Arrays.toString(arr);
			System.out.println(s);
		}

}
